#include <iostream>
#include <string>
using namespace std;

typedef struct Node
{
    char digit;
    struct Node *top;
    struct Node *rear;
} Node, *NodeList, *Stack, *Queue;

string map2[127] = {""};
string map1[127] = {""};

void Init(NodeList L)
{
    L->rear = L;
    L->top = L;
}
char Remove(Node *p)
{
    p->top->rear = p->rear;
    p->rear->top = p->top;
    char character = p->digit;
    free(p);
    return character;
}

void Append(NodeList &L, char newCharacter)
{
    //NodeList p = (NodeList)malloc(sizeof(Node));
    Node *p = (Node *)malloc(sizeof(Node));
    p->digit = newCharacter;
    p->top = L->top;
    p->rear = L;
    L->top->rear = p;
    L->top = p;
}

char Pop(NodeList &L)
{
    return Remove(L->top);
}

void Push(Stack &S, char newCharacter)
{
    Append(S, newCharacter);
}

void InQueue(Queue &Q, char newCharacter)
{
    Append(Q, newCharacter);
}

char OutQueue(Queue &Q)
{
    return Remove(Q->rear);
}

int Empty(Stack &Q)
{
    if (Q->rear == Q && Q->top == Q)
    {
        return 1;
    }
    return 0;
}

void DefaultInitMap2()
{
    map2['t'] = "天";
    map2['d'] = "地";
    map2['s'] = "上";
    map2['a'] = "一只";
    map2['e'] = "鹅";
    map2['z'] = "追";
    map2['g'] = "赶";
    map2['x'] = "下";
    map2['n'] = "蛋";
    map2['h'] = "恨";
}

void DefaultInitMap1()
{
    map1['B'] = "tAdA";
    map1['A'] = "sae";
}

void Rule1(Stack &S, char key)
{
    if (map1[key] == "")
    {
        Push(S, key);
    }
    else
    {
        for (int i = 0; i < map1[key].length(); i++)
        {
            Rule1(S, map1[key][i]);
        }
    }
}

void Rule2(Stack &S, Stack &Q)
{
    char tmpc;
    Queue tmp = (Queue)malloc(sizeof(Node));
    Init(tmp);
    do
    {
        tmpc = Pop(S);
        if (tmpc == ')')
        {
            Rule2(S, Q);
        }
        else
        {
            InQueue(tmp, tmpc);
        }
    } while (tmpc != '(');
    tmpc = Pop(tmp);
    tmpc = Pop(tmp);
    while (!Empty(tmp))
    {
        Push(Q, tmpc);
        Push(Q, OutQueue(tmp));
    }
    Push(Q, tmpc);
}

void Explain(Stack &Q, Stack &S)
{
    while (!Empty(S))
    {
        char tmpc = Pop(S);
        if (tmpc != ')')
        {
            Rule1(Q, tmpc);
        }
        else
        {
            Rule2(S, Q);
        }
    }
}

void SpeakLikeAHuman(Queue Q)
{
    while (!Empty(Q))
    {
        cout << map2[OutQueue(Q)];
    }
    cout << endl;
}

bool Prompt(string message)
{
    cout << message << "(yes/no)" << endl;
    while (1)
    {
        cin >> message;
        if (message == "yes" || message == "y")
        {
            return true;
        }
        if (message == "no" || message == "n")
        {
            return false;
        }
        cout << "非法输入，请检查。" << endl;
    }
}

void test()
{
    for (int i = 0; i < 128; i++)
    {
        if (map1[i] != "")
        {
            cout << (char) i << " = " << map1[i] << endl;
        }
    }
    for (int i = 0; i < 128; i++)
    {
        if (map2[i] != "")
        {
            cout << (char) i << " = " << map2[i] << endl;
        }
    }
}

int main()
{
    Stack S = (Stack)malloc(sizeof(Node));
    Stack Q = (Stack)malloc(sizeof(Node));
    Init(S);
    Init(Q);
    string userInput;
    if (Prompt("你希望自定义规则1吗？"))
    {
        cout << "请输入规则对应关系。示例：'B=tAdA'。输入'Done'结束。" << endl;
        while (true)
        {
            cin >> userInput;
            if (userInput == "Done")
            {
                break;
            }
            map1[userInput[0]] = userInput.substr(2);
        }
    }
    else
    {
        DefaultInitMap1();
    }
    if (Prompt("你希望自定义规则2吗？"))
    {
        cout << "请输入规则对应关系。示例：'t=天'。输入'Done'结束。" << endl;
        while (true)
        {
            cin >> userInput;
            if (userInput == "Done")
            {
                break;
            }
            map2[userInput[0]] = userInput.substr(2);
        }
    }
    else
    {
        DefaultInitMap2();
    }
    test();
    char tmp;
    cout << "请输入魔王语言，以 '?' 结尾。" << endl;
    while (cin >> tmp)
    {
        if (tmp == '?')
        {
            break;
        }
        Push(S, tmp);
    }
    Explain(Q, S);
    SpeakLikeAHuman(Q);
}